/*
Generate Parentheses Total Accepted: 6741 Total Submissions: 22178 My Submissions
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"
*/

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (!n) return res;
        string resone("");
        do_genParenthesis(0, 0, n, resone, res);
        return res;
    }
private:
    void do_genParenthesis(int left, int right, int n, string &resone, vector<string> &res) {
        if (left+right == 2*n) { res.push_back(resone); return;}
        if (left < n) {
            resone.push_back('(');
            do_genParenthesis(left+1, right, n, resone, res);
            resone.pop_back();
        }
        if (right < left) {
            resone.push_back(')');
            do_genParenthesis(left, right+1, n, resone, res);
            resone.pop_back();
        }
    }
};

#if 0
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> finalresult;
        unordered_set<string> result, newresult;
        if (n <=0) return finalresult;
        result.insert("()"); // n = 1;
        for (int i = 2; i <= n; i++) {
            for (auto it = result.begin(); it != result.end(); it++) 
                insertString(*it, newresult);
            result.clear();
            swap(result, newresult);
        }
        for (auto it = result.begin(); it != result.end(); it++) {
            finalresult.push_back(*it);
        }
        return finalresult;
    }
private:
    void insertString(const string &s, unordered_set<string> &newresult) {
        // find every '(' and insert a pair of "()"
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') 
                newresult.insert(s.substr(0, i+1) + "()" + s.substr(i+1, s.length()-i-1));
        }
        newresult.insert("()" + s);
        newresult.insert(s + "()");
    }
};
#endif
